package Offer;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author lakersUp
 * @Classname
 * @Description
 * @Date 2022/2/28 9:35
 * @Version 1.0
 */
public class Offer59maxSlidingWindow {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums==null || nums.length==0){
            return new int[]{};
        }
        Deque<Integer> queue = new ArrayDeque<>();
        int[] res=new int[nums.length-k+1];
        int j=0;
        for(int i=0;i<nums.length;i++){
            if(!queue.isEmpty() && i-queue.peekFirst()>=k){
                queue.pollFirst();
            }
            while(!queue.isEmpty() && nums[i]>=nums[queue.peekLast()]){
                queue.pollLast();
            }
            queue.offer(i);
            if((i+1)>=k){
                res[j++]=nums[queue.peekFirst()];
            }
        }
        return res;
    }
}
